package leetcode.周赛.第276场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/16 14:19
 * @description：https://leetcode-cn.com/problems/solving-questions-with-brainpower/
 */
public class 解决智力问题 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.mostPoints(new int[][]{{3, 2}, {4, 3}, {4, 4}, {2, 5}}));
    }

    /*class Solution {
        long maxPot = 0L;
        public long mostPoints(int[][] questions) {
            dfs(questions, 0, 0L);
            return maxPot;
        }

        private void dfs(int[][] questions, int i, long pot) {
            if (i >= questions.length) {
                maxPot = Math.max(maxPot, pot);
                return;
            }
            // 跳过
            dfs(questions, i + 1, pot);
            // 解决
            int[] question = questions[i];
            dfs(questions, i + question[1] + 1, pot + question[0]);

        }
    }*/
    class Solution {
        public long mostPoints(int[][] questions) {
            int n = questions.length;
            long[] dp = new long[n + 1];
            for (int i = n - 1; i >= 0; i--) {
                int doItIdx = i + questions[i][1] + 1;
                dp[i] = Math.max(dp[i + 1], questions[i][0] + (doItIdx > n ? 0 : dp[doItIdx]));
            }
            return dp[0];
        }
    }
}
